import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Solution743 {
    public int networkDelayTime(int[][] times, int n, int k) {
        int[][] map=new int[n+1][n+1];
        for (int i=1;i<=n;i++){
            Arrays.fill(map[i],-1);
        }
        for (int[] time : times) {
            map[time[0]][time[1]]=time[2];
        }
        Queue<Integer> queue=new LinkedList<>();
        queue.offer(k);
        int[] dis=new int[n+1];
        Arrays.fill(dis,Integer.MAX_VALUE/3);
        dis[k]=0;
        while (!queue.isEmpty()){
            int t=queue.poll();
            for (int i=1;i<=n;i++){
                if (map[t][i]!=-1 &&  dis[i]>dis[t]+map[t][i]){
                    if (!queue.contains(i)){
                        queue.offer(i);
                    }
                    dis[i]=dis[t]+map[t][i];
                }
            }
        }
        int ans=0;
        for (int i=1;i<=n;i++) {
            ans=Integer.max(ans,dis[i]);
        }
        return ans==Integer.MAX_VALUE/3?-1:ans;
    }

    public static void main(String[] args) {
        System.out.println(new Solution743().networkDelayTime(new int[][]{{1,2,1},{2,3,2},{1,3,4}},3,1));
    }
}
